/*
 * @lc app=leetcode.cn id=213 lang=golang
 *
 * [213] 打家劫舍 II
 */

// @lc code=start
func rob(nums []int) int {
	if len(nums) == 1 {
		return nums[0]
	}

	return max(_rob(nums[:len(nums)-1]), _rob(nums[1:]))
}

func _rob(nums []int) int {
	if len(nums) == 1 {
		return nums[0]
	}

	if len(nums) == 2 {
		return max(nums[0], nums[1])
	}

	memo := make([]int, len(nums))
	memo[0] = nums[0]
	memo[1] = max(nums[0], nums[1])

	for i := 2; i < len(nums); i++ {
		memo[i] = max(memo[i-1], memo[i-2]+nums[i])
	}
	return memo[len(nums)-1]
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

// @lc code=end

 
 